﻿using System;
using System.Collections.Generic;
using System.Text;

namespace libSecuritySystem
{
    public class Crytography
    {
        public static int BezoutAlgorithm_gcd(int a, int b, ref int x, ref int y)
        {
            int gcd = 1; //ax + by = d
            if (a < 0 || b < 0)
                return 0;
            int max = (a >= b) ? a : b;
            int min = (a < b) ? a : b;

            if (min == 0)
            {
                gcd = a;
                x = 1; y = 1;
            }
            else
            {
                int x2 = 1;
                int x1 = 0;
                int y2 = 0;
                int y1 = 1;
                int q, r;
                while (b > 0)
                {
                    q = a / b; r = a - q * b; x = x2 - q * x1; y = y2 - q * y1;
                    a = b; b = r; x2 = x1; x1 = x; y2 = y1; y1 = y;
                }
                gcd = a;
                x = x2; y = y2;
            }


            return gcd;
        }

        public static bool CheckRelativePrime(int a, int b)
        {
            bool isRelative = false;
            int x, y;
            x = y = 0;
            int gcd = BezoutAlgorithm_gcd(a, b, ref x, ref y);
            if (gcd == 0)
                return false;
            if (gcd == 1)
                isRelative = true;
            return isRelative;
        }

        public static bool CheckRelativePrimeWithArray(List<int> src, int a)
        {
            for (int i = 0; i < src.Count; i++)
            {
                if (!CheckRelativePrime(src[i], a))
                    return false;
            }
            return true;
        }

        //Not trust. This code is found on Internet.!!!!!!!
        private static int ExtendedEuclid(int a, int m)
        {
            int inverse = -1;
            int y0 = 0;
            int y1 = 1;

            int r;
            int q;
            while (a > 0)
            {
                r = m % a;
                if (r == 0)
                    break;
                q = m / a;
                inverse = y0 - y1 * q;
                m = a;
                a = r;
                y0 = y1;
                y1 = inverse;
            }

            if (a > 1)
                return -1;
            else
                return inverse;
        }

        //Find the inverse of a mod m, denoted by (a^-1 mod m)
        //if a is larger than m then calculate I = a % m
        //then find the inverse of I mod m
        public static int ModInverseIn_Zm(long a, int m)
        {
            int baseOfMod;
            int inverse = -1;
            if (a > m)
                baseOfMod = (int)(a % m);
            else
                baseOfMod = (int)a;

            int x, y;
            x = y = 0;
            int gcd = BezoutAlgorithm_gcd(baseOfMod, m, ref x, ref y);
            if (gcd > 1) //Non-existed a^-1
                return -1;
            if (gcd == 1)
            {
                int mod = x % m;
                if (mod < 0)
                    mod = m + mod;
                inverse = mod;
            }
            return inverse;
        }


    }
}
